package cn.dlc.com.graph;

import cn.dlc.com.stack.Stack;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * @author 邓立川
 * @date 2021/3/29 22:18
 * @desc 获取路径
 */
public class DepthFirstPathsTest {

    public static void main(String[] args) throws Exception{

        // 读取文件
        BufferedReader reader = new BufferedReader(new InputStreamReader(
                DepthFirstPathsTest.class.getClassLoader().
                        getResourceAsStream("road_find.txt")));

        // 第一行表示诚实数量
        int V = Integer.parseInt(reader.readLine());

        // 初始化这个图
        Graph graph = new Graph(V);

        // 第二行，城市道路条数
        int E = Integer.parseInt(reader.readLine());

        for (int i = 0; i < E; i++) {
            String road = reader.readLine(); // 得到边 0 1
            String[] str = road.split(" ");
            int start = Integer.parseInt(str[0]);
            int end = Integer.parseInt(str[1]);

            graph.addEdge(start, end);
        }

        // 构建深度路径搜索，找到从0开始的所有相通节点
        DepthFirstPaths paths = new DepthFirstPaths(graph, 0);

        System.out.println(paths.hasPathTo(4));
        System.out.println(Arrays.toString(paths.getMarked()));

        // 获取到4的路径
        Stack<Integer> stack = paths.pathTo(4);
        for (Integer integer : stack) {
            System.out.println(integer);
        }
    }
}
